View AN860_9089893.PDF datasheet online --- IC-ON-LINE

Datasheet File OCR Text:

AN860/0596 1/60 application note real-time kernels on the st20 by julian wilson this note is a preliminary look at the facilities provided by the st20 architecture for implementing a real-time kernel. 1 what is a kernel? a real-time kernel is a mechanism for controlling the execution of the tasks existing in a system. a real-time system has timing constraints governing its behaviour which mean that some actions must be carried out by particular deadlines. an example of real-time is the controlling of a fuel valve to a motor, an example of non real-time is the updating of a record in a wages data base. the important aspect of controlling the execution of tasks is that of scheduling. a real- time system must be able to perform a particular action in a particular time and thus the kernel must be able to guarantee that the task will be scheduled in a specifiable time. in other words the most important feature of a real-time kernel is that it must be deterministic. the most significant aspect of the micro-kernel built into the st20 architecture is that it is non-deterministic. this is so because a process is scheduled onto the back of a queue of unknown length. in many embedded systems this non-determinism does not matter, what matters is that the overall work rate keeps up with the actual data rate. in some environments, however, it matters a great deal and in these cases the st20 micro kernel must be enhanced. a deterministic system is one in which the time taken from the occurrence of an event and the software associated with that event running on the processor has a known maximum duration. if the maximum duration is less than the required time for the ap- plication the system should be able to support the application. a standard mechanism for providing deterministic scheduling is to implement a kernel which supports mul- tiple levels of priority in which a higher priority task will always preempt a lower priority task and the time for preemption is known. preemption is the act of suspending the current task and starting the new task. this note is concerned with the requirements for implementing a multi-priority preemptive scheduler on the st20. 1
2/60 table of contents 1whatisakernel? ............................................ 1 2whatmustitdo? ............................................. 3 3howcanitdoit? ............................................. 3 4thest20 ...................................................... 4 4.1 traps .................................................... 6 4.2 interrupts ............................................... 8 5implementationonthest20 .................................. 9 5.1 extension ............................................... 10 5.1.1 implementation . . . . . . . . . . . . . . . . . . . . . . . .................. 12 5.1.1.1 queue empty trap ................................ 16 5.1.1.2 all other traps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 5.2 replacement ............................................ 20 5.2.1 implementation . . . . . . . . . . . . . . . . . . . . . . . .................. 21 5.2.1.1 queue empty trap ................................ 22 5.2.1.2 timeslice traps . . . . . . . . . . . . . ..................... 24 5.2.1.3 all other traps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 5.3 st20highpriorityprocesses ........................... 27 6performance ...............................................28 7conclusion ................................................. 28 appendix ...................................................... 29
3/60 real-time kernels on the st20 2 what must it do? a multi-priority preemptive scheduler has a number of jobs to perform. these are: keep track of all user tasks in the system. keep track of all system resources. make certain that the highest priority runnable task is actually the task which is run- ning. provide a set of user accessible task-management functions. share the available cpu time fairly between tasks with the same priority. fail to a known safe state. recover from failure in a safe and controlled manner. protect itself and other user's tasks from errant behaviour in user's tasks. manage mutual exclusion. manage access to shared resources. additionally functions the kernel should endeavour to perform include. use the cpu efficiently. make certain that the response to external stimuli occurs as quickly as possible. provide visibility of state so that debug and monitoring tools can be implemented easily. manage priority enhancemet for access to shared resources. it can be seen that any kernel which attempts to do the above jobs must be involved in every aspect of the functioning of the cpu. in particular, the kernel must be aware of every scheduling act which takes place. 3 how can it do it? a real-time system is a collection of interacting objects which have particular charac- teristics. some of these objects are tasks. a task will have characteristics such as: priority resources owned current instruction pointer current stack pointer current state child tasks parent tasks memory range and so on. it is convenient to keep this collection of attributes in a data structure in an accessible place. the structure is usually refered to as a pd (process descriptor) and the kernel
4/60 real-time kernels on the st20 uses the set of pds to manage the tasks and to hold all current information about them. the set of pds is normally kept as a linked list which has a head and tail pointer. tasks can be added to and removed from the list using standard creation and destruction functions. the pd is the repository of all information about a task and so is effectively the task's id. other objects exist as part of a kernel. examples are queues, resources, trap han- dlers, interrupt handlers etc. all of these objects will also have some kind of of man- agement structure. the structures which describe the objects in the system are used by the kernel to control the actions requested on any object. for example, a request to kill a task would require knowledge of the task's current state, which resources it currently owns, whether the request is legal, which other tasks are dependent on the task to be killed and so on. all of this information must be available through the kernel's object data structures. it is normal to talk of a kernel as if it is a separate task running in the system which performs actions independently. this is not, normally, the case. the kernel is, usu- ally, a set of functions which are called directly or indirectly by the tasks themselves. as shall be shown in the next section, the st20 is somewhat unusual in this area. the functions which constitute the kernel perform jobs such as task creation/destruction, queue insertion and descriptor maintenance. many of these functions require privil- iges and must be completed as a single action to guarantee no invalid transient infor- mation in the system data structures. to re-cap, a real-time kernel is a set of data structures and functions which provide a mechanism for controlling access to the resources of a system in a predictable and deterministic manner. 4 the st20 the st20 microprocessor is a member of the st20 family of application targetted mi- croprocessors which have an advanced modular architecture. the individual mem- bers are created by combining a cpu core with an application orientated set of macro cells to produce an overall processor which is a custom fit to the chosen application. the cpu cores range from very small simple and low power where the primary em- phasis is on very small silicon area to high performance where the cpu may have significant work to do. the st20 is a specific variant of the architecture with a mid- range performance level targetted at the requirements for the set-top-box market. the cpu core in the st20 is the c4 core which includes a number of autonomous scheduling capabilities. the c4 core has a micro-kernel which maintains two process queues; a low-priority queue which shares cpu time between the processes on the
5/60 real-time kernels on the st20 queue by time-slicing and a high-priority queue which supports processes which must run to completion. the processor has a single serial link, a set of prioritised vectored interrupts, two timers and several external dma engines which all of which can auton- omously schedule processes onto the process queues. the native scheduling model implemented by the st20 is a cooperative non-preemp- tive model. the processes on the low-priority queue use the cpu until they become blocked or until their timeslice slot has expired. if their timeslice slot has expired they are put on the back of the low-priority queue and the process on the front of the queue is resumed from the point at which it was last descheduled. processes which become ready to run (as a result of an external stimulus or some action by the currently run- ning process) are added to the back of the queue ready to take their turn on the cpu. high-priority processes run until they become blocked, they do not time-slice and they cannot be preempted. high-priority processes always preempt low priority process and run until they cannot continue. an interrupt on a traditional microprocessor will, usually, cause some scheduling ac- tions to occur. on the st20 this mechanism is significantly extended with autono- mous scheduling occurring as the result of the following events. timeslice input message output message timer expiration process stopping semaphore wait semaphore signal traps and interrupts the first seven actions place a process on the end of one of the scheduling queues and may also cause a context switch. the cooperative scheduling model supported allows a relatively large number of light weight processes to share available cpu re- source very efficiently. when a process on the low-priority queue gives up the proc- essor if it has become blocked or if its timeslice period has expired the next process on the queue is automatically scheduled by the hardware with no software interven- tion. this hardware scheduling results in a very low context-switch time of, approxi- mately, 500 nanoseconds. the time until a process actually runs from when it is placed on the queue is unknown, however, because the queue is of unknown length. if the target system demands that this time must be less than a fixed maximum or that there must be a hierarchy between the processes active on the system then it may be necessary to implement an alternative scheduling scheme. the simplest solution to this non-determinism problem is by a clear understanding of the process model of the
6/60 real-time kernels on the st20 system, using high-priority processes for time critical actions and knowing the max- imum number of processes whic may exist on the low-priority queue at any moment. for more complex systems such a detailed knowledge may be infeasible. alternative scheduling models must be implemented by a software kernel which de- termines which process to run and manages the cpu queues. a software kernel on the st20 may be implemented as an extension to the st20 micro kernel or as a com- plete alternative to the st20 micro kernel. which of these two approaches is chosen largely depends on the features and performance required from the kernel to be im- plemented. the architecure of the st20 includes some features to assist in constructing a kernel with a richer scheduling model. these features are: traps for all scheduling actions trap on queue empty timeslice enable/disable interrupt enable/disable force timeslice queue manipulation instructions for queue insertion shadow register manipulation process restart save and restore queue pointers swap run queue swap timer queue the basic mechanism to assist the kernel writer is the scheduling trap. every time a process is about to be added to the high or low priority run queue one of the sched- uling traps will be invoked if it is enabled. 4.1 traps the st20 has four trap groups for both high and low priority, the groups are break- point, error, system and scheduler. the scheduler group is different from the others in that it does not trap exceptions but intercepts actions of the st20 micro kernel. the traps in the scheduler group are queueempty, external channel, internal channel, timer, timeslice, run, signal and processinterrupt. queueempty indicates that there is no more work to do and all of the others indicate that the hardware scheuler is about to schedule a process on a queue. trap handlers and trapped processes are set up and examined via the four instruc- tions: 1. ldtraph load trap handler structure
7/60 real-time kernels on the st20 2. sttraph store trap handler structure 3. ldtrapped load trapped process structure 4. sttrapped store trapped process structure a scheduler trap is invoked when a process is about to be run. the trapped process is the process which has been interrupted and the trap handler is the process which is invoked to handle the trap. the trapped process and the trap handler process data structure are used to pass information to the handler, to save state and to reset the state of the processor as it enters the trap handler. the handler structure enables word is used to reset the trap and global interrupt enable state of the processor and is typically set up to prevent another trap from the same group occurring while the trap handler is running to avoid reentrancy problems. the trapped process structure contains the trap bit which indicates the source of the trap. the structures are as fol- lows: the process descriptor (stack pointer + priority) of the process about to be scheduled is passed to the trap handler in traphandler stack[0]. for the scheduler traps, other than the queue empty trap, the trap handler has details of the process which has been suspended, and the process about to be scheduled and can do one of the fol- lowing: 1. priority (new) < priority (trapped) save new task on appropriate suspended queue. return to trapped task. 2. priority (new) = priority (trapped) add new process to back of current processor run queue. return to trapped task. 3. priority (new) > priority (trapped) trap handler structure enables mask word which will be anded with the trap enable and global interrupt bits. bits 15 - 0 are the trap bits mask bits 23 - 0 are the global interrupt mask base + 0 status trap handler initial status register value base + 1 wptr trap handler initial stack pointer base + 2 iptr start of trap handler code base + 3 trapped process structure enables enables register bits at time of trap base + 0 status status register at time of trap base + 1 wptr trapped task current stack pointer base + 2 iptr next instruction to execute on return from trap base + 3
8/60 real-time kernels on the st20 suspend current processor run queue, saving state of trapped task. put new task on processor run queue. invalidate trapped process state. return from trap (will select first task on the processor run queue). for the queue empty trap the trap handler must suspend the current queue and run the highest priority non-empty queue. if there is no queue available with processes to run, the queue empty trap must be disabled to prevent continuous queue empty traps occurring. the intention of the scheduler traps is to allow a real-time kernel writer to extend the capabilities of the built-in micro-kernel to implement more powerful scheduling facili- ties yet, at the same time, use the micro-code wherever possible to deliver very fast context switching. the trap handler invoked is the trap handler for the priority of the process about to be scheduled rather than the process currently executing. enabling scheduler traps only really makes sense at low priority to implement software managed scheduling. within this environment high priority processes are much more akin to interrupt handlers or pieces of hardware and should be used for time critical functions, dma handlers (e.g.links) and for watchdog processes. for many applications a combination of st20 native high-priority processes and real- time kernel scheduled low-priority tasks produces a very-efficient and flexible solution to real-world scheduling requirements. the example schedulers given in appendices b and c demonstrate this model. *******to be extended to describe all state when a scheduler trap occurs******** 4.2 interrupts the st20 supports eight prioritized external interrupts which may be configured to be at a higher or lower priority than the high priority process queue. each interrupt level has a single software handler which is initiated by the on-chip interrupt controller if the associated interrupt pin has been activated and the interrupt is enabled. an interrupt handler always pre-empts a scheduled process (i.e. not a trap handler) and any inter- rupt handler at a lower priority (0 = lowest to 7 = highest). an interrupt handler is set up by writing its wptr (stack pointer) to the appropriate handlerwptr register, setting the trigger mode in the triggermode register and then setting the matching enable bit in the mask register. the trigger mode is flexible and can be set to be edge or level and high or low. in common with standard st20 proc- esses the interrupt handler's entry point is stored in and retrieved from its stack (which is unlike a trap handler). 1
9/60 real-time kernels on the st20 5 implementation on the st20 the primary decision when implementing a software scheduler on the st20 is whether to use the hardware scheduler but extend its capabilities or replace the hard- ware scheduler completely. the answer to this depends largely on what other fea- tures the new scheduling scheme requires. if the new scheduling scheme is intended just to provide prioritized scheduling then a relatively lightweight modification of the built-in scheduler is probably the right solution. if, however, the scheduling scheme is part of a more complete real-time kernel then it may be desirable to replace the micro- kernel completely. the decision as to which type of scheduler to use is also governed by the character- istics of the target application. a typical embedded application creates a set of tasks with a fixed relationship to one another, starts them and leaves them to run until power-off. embedded applications normally have no dynamic characteristics nor any sharing of resources between tasks. in such a static environment, the cost incurred when doing some out of the ordinary action, such as killing another task, is an accept- able penalty for the benefit of very fast lightweight context switching during normal running. typical facilities offered by more ambitious real-time kernels include facilities to manage system resources, kill other tasks, promote or decay the priority of tasks, manage memory, manage time slicing and use different scheduling algorithms from round robin with time-slicing. an example of the complexity of the internals of a real-time kernel is an environment in which task t0 of priority p0 wishes to run but cannot because it needs a resource r0. r0 however is currently owned by task t1 of priority p1 where p1 is lower than p0. a third task, t2 of priority p2 where p2 is higher than p1 but lower than p0, is run- ning. as a result t0 is being blocked by the lower priority task t2. similarly intricate in- terconnections occur when tasks attempt to kill other tasks. to manage a kernel of any complexity it is necessary to to maintain data structures for all of the objects controlled by the kernel. the data structure for managing tasks is usually called a process descriptor (pd). the pd of any task is the repository of all in- formation on that task and is the handle by which any scheduling type activity is man- aged. the lists of object descriptors, especially pds, are used by the kernel to manage the system. it is imperative to the kernel that it is in control at all times and is aware of the complete state of the processor. any autonomous scheduling activity by the hard- ware must inform the kernel so that it can keep all state information complete and consistent. this is partly achieved on the st20 by enabling the scheduler traps. any 1
10/60 real-time kernels on the st20 autonomous scheduling action to place a process on the run queue is intercepted and the st20 traps to a handler when a process is about to be added to one of the queues and presents it with details of the process about to be scheduled. the stack pointer of the about to be scheduled process is passed to the trap handler in the trap handler's stack. the trap handler must determine what to do with the newly runnable task, whether to run it, queue it on the processor's run queue or place it on a currently inactive queue. how to determine the scheduling priority of the new task is the major difficulty for the kernel implementer. descheduling actions, such as waiting on a semaphore or timer do not generate traps, however, and, as a consequence, the current pd is invalidated without the kernel being informed. this is a serious problem for a more general kernel which is discussed in more detail in section 5.2. the following two sections describe a scheduling algorithm which is a lightweight ex- tension to the hardware scheduler and a more general scheduling mechanism which is suitable as the basis for building a real time operating system. 5.1 extension this section looks at the mechanisms which might be employed to implement a preemptive scheduler but still allow the built-in micro-kernel to do as much of the scheduling work as possible. the first decisions to make are what are the goals of the scheduler. for this section they are as follows: multiple priorities. pre-emptive scheduling. minimum context switch time. hardware scheduling between tasks of the same priority. the fourth goal, to use the built-in micro kernel when scheduling between tasks of the same priority, has a profound effect on the way the scheduler must work. the min- imum scheduling time occurs when the micro kernel time slices between the tasks at a particular priority with the timeslice trap disabled. whenever a new task is about to be scheduled and causes a trap the trap handler must decide if the task is higher, lower or equal in priority to the tasks on the current queue. if the new task is lower in priority it is added to the appropriate inactive queue and the currently executing task is resumed. if the new task is equal in priority it is added to the back of the cpu active queue and the currently executing task is resumed. if the new task is higher in priority the current queue must be suspended and a new queue started with the new task as the only runnable task. 1
11/60 real-time kernels on the st20 the critical action is determining the relative priority of the about to be scheduled task. the trap provides the workspace descriptor (stack pointer + st20 priority) of the new process but no other information. to determine the scheduling priority the stack pointer must be mapped to some data which gives details about the task. one possi- bility would be to compare address ranges against a task list and identify the task by its stack bounds. any form of searching is not acceptable in a real-time environment because it will be very time-consuming for all but the simplest systems and very cum- bersome if stacks can be created and destroyed dynamically. when a task is descheduled by the st20, information is stored at small negative off- sets from the workspace pointer as follows: the stack allocated to each task must accomodate these extra 5 words. a simple scheduler could be implemented easily by adding another element to this data struc- ture containing the task's priority, i.e. implementing a scheduler becomes a matter of making sure that this slot is valid whenever it needs to be. it does not need to be valid when the task is active or run- nable because the priority can be inferred from the priority of the current queue, it must be valid when the task is not runnable. the intructions which may cause a task to be unable to continue are: 1. altwt wait for one of many messages 2. in input message 3. out output message 4. outbyte output byte 5. outword output word 6. stopp stop process 7. taltwt timed wait for one of many messages 8. wait wait on semaphore making certain that the workspace -6 slot is valid when any of these 8 instructions is executed enables the trap handler to determine the priority of the process when it is about to be rescheduled. the current running priority can be maintained in a global lo- cation. the normal method of forcing the location to be valid is is to allow access to offset name function -1 iptr address of next instruction to execute -2 link link to next process on this queue -3) pointer pointer to communication data area -3) state saved state -4 tlink link to next process on timer queue (if appropriate) -5 time time process is waiting for (if appropriate) -6 priority scheduling priority of process 1
12/60 real-time kernels on the st20 these instructions only via library calls which copy the global running priority value into the designated stack slot. when the hardware micro-kernel timeslices a process it is moved to the back of the current run queue and no intervention is necessary. 5.1.1 implementation appendix b is an example implementation of a lightweight scheduler referred to as os/20 lite. also available are routines to replace all standard library functions which may cause a deschedule. the library replacement routines write the current priority into stack[-6] immediately before executing the instruction which may deschedule. the number of priorities supported is user definable - the example is set at 8. a sample user application is included in appendix d. the user task initializes the scheduler and then starts and runs the application tasks. after starting all of the ap- plication tasks the main user task enters a wait loop waiting for all of the application tasks to terminate. as each application finishes it returns to a common task exit rou- tine which signals a semaphore before terminating. preemption performance is measured by a lower-priority tasks scheduling a higher priority task using a semaphore. the lower priority task samples the time immediately before the signal and the higher priority task samples the time immediately on exiting the wait. the difference is thus the time from executing code in a lower priority task to executing code in a higher priority task including the signal and wait. this time is ap- proximately 6 microseconds. the scheduling is managed using a set of task queues, each of which corresponds to the st20 process queue. the state for each queue is maintained in a structure con- sisting of a front pointer, a back pointer, a boolean and a block of state information. the front and back pointers are workspace pointer values to be placed in the st20 cpu front and back pointers, the boolean indicates whether the queue had been in- terrupted and that the state data should be restored when the queue is restarted. the kernel maintains a single item of dynamic state - the priority of the current queue which is used to access all other state information. when an st20 is running a process, that process is not present on the processor queue, its state is the state of a number of registers in the cpu. the processor queue is a linked list of all of the processes which can run but are waiting for cpu time and has a front pointer to the next process to be run and a back pointer to the place to add newly active processes. the complete active process state thus consists of the cur- rent state of the cpu plus the queue head and tail pointers. the cpu current state consists of 12 words: enables flags status register 1
13/60 real-time kernels on the st20 workspace pointer instruction pointer stack registers (areg, breg and creg) 2d block move registers (5 words) the state data is a copy of the trapped process information which is in the same format as the shadow registers. the queue structure is thus an exact copy of the in- formation the st20 needs to restore a previous environment. the task queue struc- ture is defined in os20lite.h as typedef struct task_queue { workspace q_fptr; workspace q_bptr; bool q_suspended; state q_pstate; }queue; using the definitions: typedef unsigned long uint32; typedef unsigned long* workspace; typedef struct cpu_stack_s { uint32 c_areg; uint32 c_breg; uint32 c_creg; }cpu_stack; typedef struct cpu_state_s { uint32 c_enables; uint32 c_status; workspace c_wptr; void* c_iptr; }cpu_state; typedef struct processor_state { 1
14/60 real-time kernels on the st20 cpu_state s_cpu_state; cpu_stack s_cpu_stack; uint32 s_move2d[no_move2d_words]; }state; the first 4 words of the processor state (the enables bits, status register, workspace pointer and instruction pointer) is the state of the cpu at the time of interrupt and is identical to the contents of the trapped process structure. when a scheduler trap occurs the trap handler needs information about the running process which has been interrupted and the new process which has caused the trap. information about the interrupted process is written by the cpu into a reserved area of memory. this information can be accessed by pointing directly at the reserved memory area or it can be copied onto the trap handler's stack using the sttrapped in- struction or as follows: __asm { ldabc scheduler_trap, &trappedtask, priority_low; sttrapped; } where trapped task is declared on the local stack as trap_structure_t trappedtask; the trapped task structure returned by the sttrapped instruction is defined in the standard header file rmclib.h. it is the same structure as that used when installing a trap handler using the instruction ldtraph and is defined as typedef struct trap_structure_s { enables_word_t enables_word; status_register_t status_word; void *wptr; union { void *address; void (*handler_fn)(int /*areg*/, int /*breg*/, int / *creg*/); 1
15/60 real-time kernels on the st20 } iptr; } trap_structure_t; the cause of the trap is determined by examining the status word in the above struc- ture which is a copy of the status register and is defined in rmclib.h as typedef union status_register_u { struct { unsigned int trap_reason : 14; unsigned int unknown1 : 1; unsigned int status_trap_causeerror : 1; unsigned int scheduler_trap_priority : 2; unsigned int trap_group : 2; unsigned int timeslice_enable : 1; unsigned int unknown2 : 5; unsigned int interrupted_operation_code : 5; unsigned int process_valid : 1; } bits; unsigned int word; } status_register_t; and is tested by comparing the 14 bit trap_reason field against the enables bits as fol- lows if (trappedtask.status_word.bits.trap_reason == enable_trap_queue_empty) when a scheduler trap is taken the contents of the cpu stack and the workspace de- scriptor of the task being scheduled are written onto the trap handler's stack. the trap handler accesses these details via the trap_state_t structure which is pointed to by the compiler predefine _params (which is a mechanism for allowing any function to access its own context regardless of the number of local variables declared). _params is declared at the start of the trap handler as extern const volatile trap_state_t* _params; the trap_state structure is defined in rmclib.h as typedef struct trap_state_s { 1
16/60 real-time kernels on the st20 void *wdesc; void *gsb; int areg; int breg; int creg; } trap_state_t; the first field in this structure wdesc is the process descriptor of the process about to be scheduled while the three fields areg, breg and creg are a copy of the processor stack at the time the trap was taken and thus belong with the trapped task rather than the task causing the trap. the scheduler traps of interest to os/20-lite are the queue empty (processor idle) trap and all traps caused by an attempt to queue a process, such as may happen on signal or after a timed wait expires. os/20-lite does not enable timeslice traps. 5.1.1.1 queue empty trap the queue empty trap indicates that all of the processes on the current queue are no longer active and a new, lower priority, queue should be selected. the example os/20-lite implementation selects the next queue by a simple search down the list from the current priority. this algorithm is suitable for relatively few pri- ority levels (say 8) but may not be suitable for a high number of priority levels. another mechanism may be to keep the active queues in a linked list with a pointer to the next queue to run. the disadvantage of the second algorithm is the time taken to insert the queue into the list, which is time taken from a higher priority task whereas the simple algorithm costs time only after the higher priority task has released the processor. which mechanism is chosen is largely dependent on the system required. a system with a large number of priorities (say 256) but with only a few active at a time would benefit from the linked list whereas a system with a few priorities (say 8) would be most efficiently implemented as a simple search. if an active queue is found the cpu run queue must be loaded with the front and back pointer from the saved queue. if the new active queue had previously been inter- rupted by a higher priority queue, the cpu state must be restored from the saved state vector. the swapqueue instruction replaces the current front and back run queue pointers and the restart instruction restores all of the state but does not clear the trap reason from the saved status register. (the {{{ and }}} markers in the code are artifacts of the folding editor used to create the code and are comments when the file is seen by the compiler.) if (queue->q_suspended) 1
17/60 real-time kernels on the st20 {{{ restore the preempted queue { state* state = &queue->q_pstate; {{{ set cpu front and back pointers to values in task queue table __asm { ldabc priority_low, queue->q_fptr, queue->q_bptr; swapqueue; } }}} queue->q_suspended = false; state->s_cpu_state.c_status &= clear_trap_reason_mask; __asm { ld &queue->q_pstate; restart; } } }}} else if (queue->q_fptr != (workspace)queue_empty) {{{ select a queue and exit { __asm { ldabc priority_low, queue->q_fptr, queue->q_bptr; swapqueue; tret; } } }}} 1
18/60 real-time kernels on the st20 if no active queue is found the idle trap is disabled to prevent continuous traps being taken: trappedtask->enables_word &= (~enable_trap_queue_empty); 5.1.1.2 all other traps when any trap occurs other than the queue-empty trap, a task has become ready to run and must be added to a queue. the new task is at a lower, equal or higher priority than the current priority and so must: be queued on a waiting queue; be added to the cpu run queue or preempt the current queue. the priority of the new task is found by examining the slot in the negative workspace: workspace newwptr = (workspace)((int)(_params->wdesc) & (~priority_mask)); int newpriority = (int)newwptr[pw_priority]; lower priority adding to a lower priority queue is simply a case of updating the appropriate queue pointers: {{{ add to lower priority queue { queue* queue = taskqueue[newpriority]; if (queue->q_fptr != (workspace)queue_empty) queue->q_bptr[pw_link] = (unsigned int)newwptr; else queue->q_fptr = newwptr; queue->q_bptr = newwptr; } }}} equal priority adding to the same priority queue is done by putting the task at the back of the cur- rent processor queue: {{{ add to cpu run queue { __asm { ld _params->wdesc; 1
19/60 real-time kernels on the st20 runp; } } }}} higher priority if the new task is at a higher priority than the current priority, the current task and cpu state must be saved to the appropriate queue and the new task run. saving the cur- rent task is performed by collecting and storing the 12 state words as follows: state = &(currentqueue->q_pstate); {{{ save state of current task __asm { ldabc move2d_save_mask, priority_low, state; stshadow; /* save block move state */ ldabc abc_size_in_bytes, &state->s_cpu_stack, &areg; move; /* copy a, b and c from params */ ldabc scheduler_trap, &state->s_cpu_state, priority_low; sttrapped; /* copy trapped task state */ } }}} currentqueue->q_suspended = true; loading the new queue is a combination of initialising the cpu run queue and marking the trapped process as invalid. the swapqueue instruction leaves the pre- vious values on the cpu stack so that they can be saved into the appropriate place in the data structure: {{{ load new front and back pointers and save old __asm { ldabc priority_low, newwptr, newwptr; swapqueue; stab currentqueue->q_fptr, currentqueue->q_bptr; } 1
20/60 real-time kernels on the st20 }}} trappedtask.status_word.bits.process_valid = false; currentpriority = newpriority; the mechanisms described in this section deliver a fast lightweight multi-priority preemptive scheduler which uses the micro coded queue manipulation facilities to im- plement timeslicing between tasks of the same priority. if the kernel needs to be in- volved whenever a task switch occurs a more intrusive scheduling regime must be implemented. an example of such a mechanism follows in the next section. 5.2 replacement os/20-lite is suitable when very lightweight and fast scheduling is desired. a more complicated real-time kernel has a great deal more to manage than just the sched- uling and must determine which task to run at all times. typically such a kernel cannot allow any autonomous scheduling actions by the hardware scheduler. a task now needs to be identified by a task descriptor and it is this descriptor which must be stored at workspace slot -6 to identify the task during a scheduling action. it is also necessary to know the state of each task all of the time so that it can be manipulated as needed. it is desirable to be able to implement such a kernel by enabling the timeslice trap and to allow the micro-kernel to manage the run queue but trapping into the kernel on scheduling activity, timeslice and queue empty. the problem is that some scheduling actions, such as timeslice, trigger a trap and some, such as wait, do not. to accomo- date this either two separate mechanisms must be used to manage the tasks or the library routines for wait, in, out etc would need to simulate a scheduling trap. traps can be forced using the causeerror instruction but complicate the trap handler and quite often will be unnecessary because the instruction may not cause a deschedule. to avoid the dilemma, an alternative approach, and one favoured by developers porting an existing real-time kernel is to run with an empty run queue. all scheduling traps, the timeslice trap and the queue empty (which is really processor idle) trap are enabled. any action by the cpu to remove the process from the processor causes a queue-empty trap, any action to schedule a process causes a scheduler trap and a timeslice causes a timeslice trap. all scheduling activity, thus, causes a trap which can be monitored by the kernel. in this environment the running process continues until: it is blocked and a queue empty trap occurs a scheduling trap is taken for another task 1
21/60 real-time kernels on the st20 the timeslice period expires the kernel now has complete control of all scheduling and is aware of every state change and the state of every managed object in the system. 5.2.1 implementation appendix c is an example implementation of a scheduler referred to as os/20. also available are routines to replace all standard library functions which may cause a de- schedule. the replacement routines write the current task into stack[-6] immediately before calling the instruction which may deschedule. the sample user application described for os/20-lite and included in appendix d is the same for both os/20 and os/20-lite. one difference from os/20-lite is that the wait task has a task structure created for it so that it is a normal o/20 task which can be queued and dequeued like any other. the preemption performance is measured in an identical manner and is approximately 6 microseconds. timeslice performance of os/20 is, obviously, much worse than that of os/20-lite. the scheduling is managed using a set of task queues. the tasks are linked in a simple list with a head and tail pointer, a boolean, a block of state information and a task pointer. the front and back pointers are pointers to task structures, the boolean indicates whether the queue had been interrupted and that the state data should be restored when the queue is restarted and the additional task pointer is a pointer to the data structure for the suspended task. the scheduler maintains two items of dynamic state, a current task as well as a current priority but it is the current task which is written to stack[-6] when a task is descheduled. the st20 cpu run queue is not used at all, all task switching is achieved by reading from and writing to the trap structure so that the cpu returns from the trap directly to the task selected to run after the trap. in os/20-lite if a new task was to be executed as a result of a trap, the trap structure was modified to indicate that the current task was no longer valid and the new task was added to the front of the cpu run queue. the decision not to use the cpu queues frees the implementor from the need to maintain the task queue as a linked list of workspace pointers using the pw_link slot (-2) of the workspace. two sample implementations are provided. the first imple- mentation removes each process from the queue when it becomes the active process putting it onto the back of the queue when it is timesliced. the second implementation maintains a circular list, updating the front and back pointers when a timeslice occurs. not surprisingly, the first implementation is faster at preemption but slower at times- licing. the remainder of this section refers to the first of these two implementations. the queue and task structures are defined in os20.h as typedef struct queue_s 1
22/60 real-time kernels on the st20 { task* q_front; task* q_back; bool q_suspended; state q_pstate; task* q_task; }queue; typedef struct task_s { workspace t_wptr; /* current workspace pointer */ void* t_iptr; /* current instruction pointer */ struct task_s* t_link; /* link to next task in this queue */ int t_id; /* id of this task */ int t_priority; /* task priority */ task_state t_state; /* current state */ unsigned int* t_stack_base; /* pointer to base of stack */ int t_stack_size; /* size of stack in bytes */ }task; the q_pstate state vector is identical to that described for for os/20-lite: access to information about the running process which has been interrupted, the new process which has caused the trap and the reason for the trap is obtained in exactly the same manner as before. the scheduler traps of interest to os/20 are the queue empty (processor idle) trap, the timeslice trap and all traps caused by an attempt to queue a process, such as may happen on signal or after a timed wait expires. 5.2.1.1 queue empty trap the queue empty trap indicates that all of the processes on the current queue are no longer active and a new, lower priority, queue should be selected. 1
23/60 real-time kernels on the st20 the example os/20 implementation selects the next queue by maintaining an active queue register with a bit set for each active queue. the highest order set bit is found by use of the norm instruction. if an active queue is found the cpu must be loaded with either the task at the front of the queue or the task which was running when the queue was preeempted. resumption after preemption is implemented as follows: {{{ restore the preempted process { state* state = &queue->q_pstate; currenttask = queue->q_task; queue->q_suspended = false; if (queue->q_front == (task*)queue_empty) queueactive ^= 1 << currentpriority; state->s_cpu_state.c_status &= clear_trap_reason_mask; __asm { ld state; restart; } } }}} selecting a new task from the front of the queue: {{{ remove and run only the front process { task* front = queue->q_front; currenttask = front; queue->q_front = front->t_link; if (queue->q_front == (task*)queue_empty) queueactive ^= 1 << currentpriority; {{{ copy front details into trappedtask structure trappedtask->status_word.bits.process_valid = true; trappedtask->wptr = (int*)front->t_wptr; 1
24/60 real-time kernels on the st20 trappedtask.->iptr.address = (void*)front- >t_iptr; }}} __asm {tret;} } }}} if no active queue is found the idle trap is disabled to prevent continuous traps being taken: 5.2.1.2 timeslice traps when a timeslice trap occurs it may be necessary to replace the current task. if so, the only state which must be saved is the current workspace pointer and the current instruction pointer as all other possible state is not valid at a timeslice point. the timeslice trap code thus links the current task onto the back of the current queue and takes a new task from the front of the queue as the current task. a refinement on this algorithm would be to allocate tasks multiple timeslice slots ac- cording to a priority or need scheme and only replace the task when the allocated number of timeslice periods has expired. a scheme which allocated a percentage of cpu time according to priority could be implemented in this manner. if no other task is available at the current priority the trap handler just exits back to the interrupted task. {{{ replace the current task { queue* queue = taskqueue[currentpriority]; if (queue->q_front != (task*)queue_empty) { task* oldtask = currenttask; task* newtask; {{{ put current task at back of queue oldtask->t_wptr = (workspace)trappedtask.wptr; oldtask->t_iptr = (void*)trappedtask.iptr.address; oldtask->t_link = (task*)queue_empty; queue->q_back->t_link = oldtask; queue->q_back = oldtask; 1
25/60 real-time kernels on the st20 }}} {{{ access front of queue and write to trapped task struc- ture newtask = queue->q_front; trappedtask->wptr = (int*)newtask->t_wptr; trappedtask->iptr.address = newtask->t_iptr; queue->q_front = newtask->t_link; currenttask = newtask; }}} } } }}} priority modification it is sometimes desirable to increase or decrease the priority of the executing task. this is achieved in os/20 using the timeslice trap. the priority in the task structure is modified to the new value and a timeslice is forced. on receipt of the timeslice trap the trap handler either updates the current priority or dequeues the current task onto a lower priority. because no tasks are on the cpu queue increasing the priority con- sists of nothing more than updating the current priority value. int taskpriority = currenttask->t_priority; if (taskpriority == currentpriority) ... replace the current task else if (taskpriority > currentpriority) {{{ task is raising its priority - just reset current priority currentpriority = taskpriority; }}} else {{{ task is lowering its priority - put on back of appropriate queue { queue* queue = taskqueue[taskpriority]; task* oldtask = currenttask; oldtask->t_wptr = (workspace)trappedtask.wptr; 1
26/60 real-time kernels on the st20 oldtask->t_iptr = (void*)trappedtask.iptr.address; oldtask->t_link = (task*)queue_empty; if (queue->q_front != (task*)queue_empty) queue->q_back->t_link = oldtask; else queue->q_front = oldtask; queue->q_back = oldtask; queueactive |= 1 << currentpriority; trappedtask->status_word.bits.process_valid = false; } }}} __asm {tret;} 5.2.1.3 all other traps when any trap occurs other than the above two traps, a task has become ready to run and must be added to a queue. the new task is at a lower, equal or higher priority than the current priority and so must: be queued on a waiting queue or preempt the current queue. the priority of the new task is found by examining the data in the task structure which has been obtained from the slot in the negative workspace: workspace newwptr; task* newtask; newwptr = (workspace)((int)(_params->wdesc) & (~priority_mask)); newtask = (task*)newwptr[pw_task]; newpriority = newtask->t_priority; lower or equal priority adding to a lower priority queue is simply a case of updating the appropriate queue pointers: {{{ add to lower priority queue { queue* queue = taskqueue[newpriority]; newtask->t_wptr = newwptr; newtask->t_iptr = (void*)newwptr[pw_iptr]; newtask->t_link = (task*)queue_empty; 1
27/60 real-time kernels on the st20 if (queue->q_front != (task*)queue_empty) queue->q_back->t_link = newtask; else queue->q_front = newtask; queue->q_back = newtask; queueactive |= 1 << newpriority; } }}} higher priority if the new task is at a higher priority than the current priority, the current task and cpu state must be saved to the appropriate queue and the new task run. saving the cur- rent task is performed by collecting and storing the 12 state words as shown for os/ 20-lite with the addition of the requirement to save the current task and update the queue active bit. currentqueue->q_task = currenttask; queueactive |= 1 << currentpriority; loading the new task is done by resetting the global values and writing to the trapped process structure. currentpriority = newpriority; currenttask = newtask; {{{ reset status bits in trappedtask structure trappedtask->wptr = (int*)newwptr; trappedtask->iptr.address = (void*)newwptr[pw_iptr]; }}} __asm {tret;} the mechanisms described in this section deliver much of the functionality needed for building a full featured real-time operating system taking advantage of the features provided by the st20. because both the st20 state and the os/20 state is small the context switching time is kept well inside 10 microseconds which compares favour- ably with proprietary real-time kernels on other microprocessors. 5.3 st20 high priority processes the st20 maintains a separate queue for high and low priority processes. processes on the high priority queue run until they are blocked, they do not timeslice and cannot 1
28/60 real-time kernels on the st20 be pre-empted (except by higher priority interrupt handlers as described earlier). processes on the low priority queue share the cpu using a round-robin timeslicing scheme and will always be pre-empted by high priority processes and interrupt han- dlers. the mechanisms described in this application note are designed to implement a multi priority scheduling regime on the low priority queue only. the high priority queue may be used as a completely separate scheduling mecha- nism to provide an exceptionally low latency pre-emption mechanism for extremely time critical actions. the low to high pre-emption time is of the order of 600 nanosec- onds (compared with the 5 - 7 microseconds of os/20). it must, however, be remem- bered that high priority processes cannot be usurped from the cpu so should be used in much the same manner as interrupt handlers on other microprocessors. a high priority process would typically wake up, grab some data, signal a worker process that data is available then go back to sleep. using this model and one of the multi-priority scheduling schemes described an extremely powerful and flexible, ap- plication sympathetic kernel can be constructed. the trap mechansim as implemented disables all interrupts while the trap handler is running. 6 performance 7 conclusion this note has shown that the combination of the st20 micro scheduler and the scheduler traps enable a highly efficient application sympathetic kernel to be con- structed with very low cost. such a kernel has a number of advantages over proprie- tary real-time kernels. no royalty payment very fast context switch (<6 microseconds) completely customisable to application requirements small size hardware / software ratio can be adjusted as desired st20 toolset compatible available in source form where the scheduling needs of the application cannot be met by the native coopera- tive scheduling algorithm of the st20 the facilities provided by os/20 offer a realistic alternative 1
29/60 real-time kernels on the st20 appendix a. details of available state information when within a trap handler. b. appendix b {{{ title /************************************************************* * * * module : os20lite.c * * purpose : st20-tp1 kernel (os/20-lite) scheduler trap * * handler * * author : julian wilson december 1995 * * * ************************************************************/ }}} {{{ includes #include #include #include #include oos20lite.ho #include olibrary.ho }}} {{{ globals int* currentpriorityptr; }}} {{{ statics private semaphore taskcomplete; private int activetasks = 0; private task* tasklist[max_tasks]; private int taskcount; }}} {{{ test globals 1
30/60 real-time kernels on the st20 int higherschedules = 0; int equalschedules = 0; int lowerschedules = 0; int idleschedules = 0; int newqueues = 0; int idles = 0; int resumes = 0; }}} {{{ functions {{{ void* internal_memory_allocate (size_t requested) private void* internal_memory_allocate (size_t requested) { private unsigned int address = memstart; private int available = reserved_internal; void* memory = null; int claimed; if (available > requested) { memory = (void*)address; claimed = (requested + (bytes_per_word - 1)) & word_mask; address += claimed; /*printf (oclaimed %d bytes up to address %8x\no, claimed, address - 1);*/ } return memory; } }}} {{{ void kernel_scheduler (int areg, int breg, int creg) {{{ tell compiler this is the trap handler void kernel_scheduler (int areg, int breg, int creg); #pragma ims_trap_handler (kernel_scheduler) }}} 1
31/60 real-time kernels on the st20 void kernel_scheduler (int areg, int breg, int creg) { extern const /*volatile*/ trap_state_t* _params; {{{ declare and place stacktics (on stack statics) queue** taskqueue; trap_structure_t* trappedtask; int currentpriority; #pragma ims_place_at_workspace_offset (taskqueue, 9) #pragma ims_place_at_workspace_offset (trappedtask, 8) #pragma ims_place_at_workspace_offset (currentpriority, 7) }}} if (trappedtask->status_word.word & enable_trap_queue_empty) {{{ find next highest priority active queue { queue* queue; for (--currentpriority; currentpriority >= 0; currentpri- ority--) { queue = taskqueue[currentpriority]; if (queue->q_suspended) {{{ restore the preempted queue { state* state = &queue->q_pstate; /*resumes++;*/ {{{ set cpu front and back pointers to values in task queue table __asm { ldabc priority_low, queue->q_fptr, queue- >q_bptr; swapqueue; } 1
32/60 real-time kernels on the st20 }}} queue->q_suspended = false; state->s_cpu_state.c_status &= clear_trap_reason_mask; __asm { ld &queue->q_pstate; restart; } } }}} else if (queue->q_fptr != (workspace)queue_empty) {{{ select a queue and exit { /*newqueues++;*/ __asm { ldabc priority_low, queue->q_fptr, queue- >q_bptr; swapqueue; tret; } } }}} } idles++; {{{ disable idle trap trappedtask->enables_word &= (~enable_trap_queue_empty); }}} } }}} else 1
33/60 real-time kernels on the st20 {{{ schedule the process onto a queue { int newpriority; workspace newwptr; newwptr = (workspace)((int)(_params->wdesc) & (~priority_mask)); newpriority = (int)newwptr[pw_priority]; if (newpriority > currentpriority) {{{ replace current queue if there is one { /*higherschedules++;*/ if (currentpriority < 0) {{{ cpu was idle, enable idle trap and load new queue { trappedtask->enables_word |= enable_trap_queue_empty; {{{ load new front and back pointers __asm { ldabc priority_low, newwptr, newwptr; swapqueue; } }}} } }}} else {{{ replace current queue { queue* currentqueue = taskqueue[currentpriority]; state* state = &(currentqueue->q_pstate); {{{ save current state __asm 1
34/60 real-time kernels on the st20 { #if 0 ldabc move2d_save_mask, priority_low, state; stshadow; /* save shadow information */ #endif ldabc abc_size_in_bytes, &state->s_cpu_stack, &areg; move; /* copy a, b and c from params */ ldabc scheduler_trap, &state->s_cpu_state, priority_low; sttrapped; /* copy trapped task state */ } }}} {{{ load new front and back pointers and save old __asm { ld newwptr; dup; ld priority_low; swapqueue; stab currentqueue->q_fptr, currentqueue- >q_bptr; } }}} trappedtask->status_word.bits.process_valid = false; currentqueue->q_suspended = true; } }}} {{{ currentpriority = newpriority; __asm { 1
35/60 real-time kernels on the st20 ld newpriority; st currentpriority; } }}} __asm {tret;} } }}} else if (newpriority == currentpriority) {{{ add to cpu run queue { /*equalschedules++;*/ __asm { ld _params->wdesc; runp; } } }}} else {{{ add to lower priority queue { queue* queue = taskqueue[newpriority]; /*lowerschedules++;*/ if (queue->q_fptr != (workspace)queue_empty) queue->q_bptr[pw_link] = (unsigned int)newwptr; else queue->q_fptr = newwptr; queue->q_bptr = newwptr; } }}} } }}} 1
36/60 real-time kernels on the st20 {{{ registers for trapped task __asm { ldabc areg, breg, creg; } }}} } }}} {{{ bool kernel_start (int prioritylevels) bool kernel_start (int prioritylevels) { task* task; queue* taskqueue; queue** taskqueueptr; int startuppriority = prioritylevels - 1; {{{ malloc space for and intialise queues and lists { int i; taskqueueptr = internal_memory_allocate (sizeof(queue*) * prioritylevels); taskqueue = internal_memory_allocate (sizeof(queue) * prioritylevels); for (i = 0; i < prioritylevels; i++) { taskqueueptr[i] = &taskqueue[i]; taskqueue[i].q_fptr = (workspace)queue_empty; /*taskqueue[i].q_active = false;*/ taskqueue[i].q_suspended = false; } task = internal_memory_allocate (sizeof(task) * max_tasks); for (i = 0; i < max_tasks; i++) tasklist[i] = &task[i]; 1
37/60 real-time kernels on the st20 } }}} {{{ initialise global state taskcount = 0; seminit (&taskcomplete, 0); }}} {{{ create trap handler environment and install it { int* handlerworkspace; handlerworkspace = internal_memory_allocate (trap_ws_size); if (handlerworkspace == null) return false; install_trap_handler (trap_group_scheduler, priority_low, (enables_word_t)everything_disabled, default_status_register, handlerworkspace, trap_ws_size, kernel_scheduler); handlerworkspace[trap_ws_words - (handler_params + 1)] = (int)taskqueueptr; handlerworkspace[trap_ws_words - (handler_params + 2)] = (int)low_trapped_task; handlerworkspace[trap_ws_words - (handler_params + 3)] = startuppriority; currentpriorityptr = &handlerworkspace[trap_ws_words - (handler_params + 3)]; } }}} {{{ enable desired traps enable_traps (enable_trap_internal_channel | enable_trap_external_channel | enable_trap_timer | 1
38/60 real-time kernels on the st20 enable_trap_run | enable_trap_signal | enable_trap_queue_empty, priority_low); }}} return true; } }}} {{{ void kernel_end (void) void kernel_end (void) { while (activetasks > 0) { os20semwait (&taskcomplete); activetasks--; } disable_traps (enable_trap_internal_channel | enable_trap_external_channel | enable_trap_timer | enable_trap_run | enable_trap_signal | enable_trap_queue_empty, priority_low); } }}} {{{ void task_end (void) private void task_end (void) { __asm{ajw -4;}; semsignal (&taskcomplete); __asm {stopp;}; } 1
39/60 real-time kernels on the st20 }}} {{{ task* task_create (void (*function)(), int stacksize, int priority, int paramwords, ...) task* task_create (void (*function)(), int stacksize, int pri- ority, int paramwords, ...) {{{ stack layout at startup /***********************************************************/ /* */ /* 2 first user param */ /* 1 param 1 global static base */ /* 0 return address */ /* -1 entry point */ /* -2 undefined */ /* -3 undefined */ /* -4 undefined */ /* -5 undefined */ /* -6 priority */ /* */ /************************************************************/ }}} { {{{ locals extern const volatile void* _params; task* task; unsigned int* stack; int i; int* paramlist = (int*)((char*)¶mwords + size- of(int)); params* globalparams = (params*)_params; }}} {{{ check the task list if (taskcount >= max_tasks) 1
40/60 real-time kernels on the st20 return null; task = tasklist[taskcount]; }}} {{{ malloc task stack if (stacksize < default_stack_size) stacksize = default_stack_size; stack = (unsigned int*)malloc (stacksize); if (stack == null) return null; }}} {{{ initialise task structure task->t_id = taskcount++; task->t_state = t_created; task->t_stack_base = stack; task->t_stack_size = stacksize; task->t_wptr = (workspace)((byte*)stack + (stacksize - (bytes_per_word * (paramwords + 4)))); task->t_priority = priority; }}} {{{ initialise positive workspace with params and return ad- dress task->t_wptr[0] = (int)task_end; /* return address */ task->t_wptr[1] = (int)globalparams->gsb; /* global static base */ for (i = 0; i < paramwords; i++) task->t_wptr[i + 2] = paramlist[i]; }}} {{{ initialise negative workspace ready to start task->t_wptr[pw_iptr] = (int)function; task->t_wptr[pw_priority] = priority; }}} {{{ register with inquest if necessary
41/60 real-time kernels on the st20 /* #ifdef inquest { int childiptr, parentwptr; __asm { ldlp 0; st parentwptr; ld (int)task->t_wptr; ldnl -1; st childiptr; } imsrtl_informthreadbirth ((void*)childiptr, (void*)parentwptr, (void*)task->t_stack_base, (void*)(task->t_stack_base + task- >t_stack_size)); } #endif */ }}} {{{ start the task task->t_state = t_active; activetasks++; __asm { ld (int)task->t_wptr; ldpri; or; runp; /* this will cause a trap and put the task on the correct queue */ } }}}
42/60 real-time kernels on the st20 return task; } }}} }}} c. appendix c {{{ title ************************************************************** * * * module : os20.c * * purpose : st20 kernel (os/20) scheduler trap handler * * * * author : julian wilson march 1996 * * * *************************************************************/ }}} {{{ includes #include #include #include #include oos20.ho #include olibrary.ho }}} {{{ globals task** currenttaskptr; }}} {{{ statics private int* currentpriorityptr; private semaphore taskcomplete; private int activetasks = 0; private task* tasklist[max_tasks]; private int taskcount;
43/60 real-time kernels on the st20 }}} {{{ test globals int higherschedules = 0; int equalschedules = 0; int lowerschedules = 0; int idleschedules = 0; int newqueues = 0; int idles = 0; int resumes = 0; int timeslices = 0; }}} {{{ functions {{{ void* internal_memory_allocate (size_t requested) private void* internal_memory_allocate (size_t requested) { private unsigned int address = memstart; private int available = reserved_internal; void* memory = null; int claimed; if (available > requested) { memory = (void*)address; claimed = (requested + (bytes_per_word - 1)) & word_mask; address += claimed; /*printf (oclaimed %d bytes up to address %8x\no, claimed, address - 1);*/ } return memory; } }}} {{{ void kernel_scheduler (int areg, int breg, int creg) {{{ tell compiler this is the trap handler
44/60 real-time kernels on the st20 void kernel_scheduler (int areg, int breg, int creg); #pragma ims_trap_handler (kernel_scheduler) }}} void kernel_scheduler (int areg, int breg, int creg) { extern const /*volatile */trap_state_t* _params; {{{ declare and place stacktics (on stack statics) int queueactive; queue** taskqueue; trap_structure_t* trappedtask; task* currenttask; int currentpriority; #pragma ims_place_at_workspace_offset (queueactive, 9) #pragma ims_place_at_workspace_offset (taskqueue, 8) #pragma ims_place_at_workspace_offset (trappedtask, 7) #pragma ims_place_at_workspace_offset (currenttask, 6) #pragma ims_place_at_workspace_offset (currentpriority, 5) }}} if ((trappedtask->status_word.word & enable_trap_queue_empty) != 0) {{{ find next task (on current or lower queue) { {{{ find active queue by looking at highest set bit in queueactive __asm { ldab 0, queueactive; norm; pop; pop; ldc max_priority; rev;
45/60 real-time kernels on the st20 diff; st currentpriority; } }}} if (currentpriority > 0) { queue* queue = taskqueue[currentpriority]; if (queue->q_suspended) {{{ restore the preempted process { state* state = &queue->q_pstate; /*resumes++;*/ {{{ currenttask = queue->q_task; __asm { ld queue->q_task; st currenttask; } }}} queue->q_suspended = false; if (queue->q_front == (task*)queue_empty) {{{ queueactive ^= 1 << currentpriority; __asm { ldab currentpriority, 1; shl; ld queueactive; xor; st queueactive; } }}} state->s_cpu_state.c_status &=
46/60 real-time kernels on the st20 clear_trap_reason_mask; __asm { ld state; restart; } } }}} else {{{ remove and run only the front process { task* front = queue->q_front; /*newqueues++;*/ {{{ currenttask = front; __asm { ld front; st currenttask; } }}} queue->q_front = front->t_link; if (queue->q_front == (task*)queue_empty) {{{ queueactive ^= 1 << currentpriority; __asm { ldab currentpriority, 1; shl; ld queueactive; xor; st queueactive; } }}}
47/60 real-time kernels on the st20 {{{ copy front details into trappedtask structure trappedtask->status_word.bits.process_valid = true; trappedtask->wptr = (int*)front- >t_wptr; trappedtask->iptr.address = (void*)front->t_iptr; }}} __asm {tret;} } }}} } /*idles++;*/ {{{ disable idle trap trappedtask->enables_word &= (~enable_trap_queue_empty); }}} } }}} else if ((trappedtask->status_word.word & enable_trap_timeslice) != 0) {{{ put the process onto the back of the current queue { int taskpriority = currenttask->t_priority; if (taskpriority == currentpriority) {{{ timeslice the task { queue* queue = taskqueue[currentpriority]; /*timeslices++;*/ if (queue->q_front != (task*)queue_empty) { task* oldtask = currenttask; task* newtask; {{{ put current task at back of queue
48/60 real-time kernels on the st20 oldtask->t_wptr = (workspace)trappedtask->wptr; oldtask->t_iptr = (void*)trappedtask- >iptr.address; oldtask->t_link = (task*)queue_empty; queue->q_back->t_link = oldtask; queue->q_back = oldtask; }}} {{{ access front of queue and write to trapped task structure newtask = queue->q_front; trappedtask->wptr = (int*)newtask->t_wptr; trappedtask->iptr.address = newtask->t_iptr; queue->q_front = newtask->t_link; {{{ currenttask = newtask; __asm { ld newtask; st currenttask; } }}} }}} } } }}} else if (taskpriority > currentpriority) {{{ task is raising its priority - just reset current priority {{{ currentpriority = taskpriority; __asm { ld taskpriority; st currentpriority;
49/60 real-time kernels on the st20 } }}} }}} else {{{ task is lowering its priority - put on back of appropriate queue { queue* queue = taskqueue[taskpriority]; task* oldtask = currenttask; oldtask->t_wptr = (workspace)trappedtask->wptr; oldtask->t_iptr = (void*)trappedtask->iptr.address; oldtask->t_link = (task*)queue_empty; if (queue->q_front != (task*)queue_empty) queue->q_back->t_link = oldtask; else queue->q_front = oldtask; queue->q_back = oldtask; {{{ queueactive |= 1 << taskpriority; __asm { ldab taskpriority, 1; shl; ld queueactive; or; st queueactive; } }}} trappedtask->status_word.bits.process_valid = false; } }}} __asm {tret;} }
50/60 real-time kernels on the st20 }}} else {{{ schedule the process onto a queue { workspace newwptr = (workspace)((int)_params->wdesc & (~priority_mask)); task* newtask = (task*)newwptr[pw_task]; int newpriority = newtask->t_priority; if (newpriority > currentpriority) {{{ replace current queue if there is one { /*higherschedules++;*/ if (currentpriority < 0) {{{ cpu was idle, set trap bits to valid { trappedtask->enables_word |= enable_trap_queue_empty; trappedtask->status_word.bits.process_valid = true; } }}} else {{{ save current state { queue* currentqueue = taskqueue[currentpriority]; state* state = &(currentqueue->q_pstate); __asm { #if 0 ldabc move2d_save_mask, priority_low, state; stshadow; /* save move 2d information */ #endif ldabc abc_size_in_bytes, &state->s_cpu_stack,
51/60 real-time kernels on the st20 &areg; move; /* copy a, b and c from params */ ldabc scheduler_trap, &state->s_cpu_state, priority_low; sttrapped; /* copy trapped task state */ } currentqueue->q_suspended = true; currentqueue->q_task = currenttask; {{{ queueactive |= 1 << currentpriority; __asm { ldab currentpriority, 1; shl; ld queueactive; or; st queueactive; } }}} } }}} {{{ currentpriority = newpriority; __asm { ld newpriority; st currentpriority; } }}} {{{ currenttask = newtask; __asm { ld newtask; st currenttask;
52/60 real-time kernels on the st20 } }}} {{{ reset workspace and iptr in trappedtask structure trappedtask->wptr = (int*)newwptr; trappedtask->iptr.address = (void*)newwptr[pw_iptr]; }}} __asm {tret;} } }}} else {{{ add to lower priority queue { queue* queue = taskqueue[newpriority]; /*lowerschedules++;*/ newtask->t_wptr = newwptr; newtask->t_iptr = (void*)newwptr[pw_iptr]; newtask->t_link = (task*)queue_empty; if (queue->q_front != (task*)queue_empty) queue->q_back->t_link = newtask; else queue->q_front = newtask; queue->q_back = newtask; {{{ queueactive |= 1 << newpriority; __asm { ldab newpriority, 1; shl; ld queueactive; or; st queueactive; } }}}
53/60 real-time kernels on the st20 {{{ restore registers for trapped task __asm { ldabc areg, breg, creg; } }}} } }}} } }}} } }}} {{{ bool kernel_start (int prioritylevels) bool kernel_start (int prioritylevels) { task* task; queue* taskqueue; queue** taskqueueptr; int startuppriority = prioritylevels - 1; int queueactive; {{{ malloc space for and intialise queues and lists { int i; taskqueueptr = internal_memory_allocate (sizeof(queue*) * prioritylevels); taskqueue = internal_memory_allocate (sizeof(queue) * prioritylevels); for (i = 0; i < prioritylevels; i++) { taskqueueptr[i] = &taskqueue[i]; taskqueue[i].q_front = (task*)queue_empty; taskqueue[i].q_suspended = false;
54/60 real-time kernels on the st20 } task = internal_memory_allocate (sizeof(task) * max_tasks); for (i = 0; i < max_tasks; i++) tasklist[i] = &task[i]; } }}} {{{ initialise global state taskcount = 0; queueactive = 0; seminit (&taskcomplete, 0); }}} {{{ create kernel task task = tasklist[taskcount]; task->t_id = taskcount++; task->t_state = t_active; task->t_priority = startuppriority; task->t_link = (task*)queue_empty; taskqueue[startuppriority].q_front = (task*)queue_empty; taskqueue[startuppriority].q_back = (task*)queue_empty; }}} {{{ create trap handler environment and install it { int* handlerworkspace; handlerworkspace = internal_memory_allocate (trap_ws_size); if (handlerworkspace == null) return false; install_trap_handler (trap_group_scheduler, priority_low, (enables_word_t)everything_disabled, default_status_register, handlerworkspace, trap_ws_size,
55/60 real-time kernels on the st20 kernel_scheduler); handlerworkspace[trap_ws_words - (handler_params + 1)] = queueactive; handlerworkspace[trap_ws_words - (handler_params + 2)] = (int)taskqueueptr; handlerworkspace[trap_ws_words - (handler_params + 3)] = (int)low_trapped_task; handlerworkspace[trap_ws_words - (handler_params + 4)] = (int)task; handlerworkspace[trap_ws_words - (handler_params + 5)] = startuppriority; currenttaskptr = (task**)&handlerworkspace[trap_ws_words - (handler_params + 4)]; currentpriorityptr = &handlerworkspace[trap_ws_words - (handler_params + 5)]; } }}} {{{ enable desired traps enable_traps (enable_trap_internal_channel | enable_trap_external_channel | enable_trap_timer | enable_trap_run | enable_trap_signal | /*enable_trap_timeslice |*/ enable_trap_queue_empty, priority_low); }}} return true; } }}} {{{ void kernel_end (void) void kernel_end (void) {
56/60 real-time kernels on the st20 while (activetasks > 0) { os20semwait (&taskcomplete); activetasks--; } disable_traps (enable_trap_internal_channel | enable_trap_external_channel | enable_trap_timer | enable_trap_run | enable_trap_signal | enable_trap_timeslice | enable_trap_queue_empty, priority_low); } }}} {{{ void task_end (void) private void task_end (void) { __asm{ajw -4;}; semsignal (&taskcomplete); __asm {stopp;}; } }}} {{{ task* task_create (void (*function)(), int stacksize, int priority, int paramwords, ...) task* task_create (void (*function)(), int stacksize, int pri- ority, int paramwords, ...) {{{ stack layout at startup /***********************************************************/ /* */ /* 2 first user param */ /* 1 param 1 global static base */
57/60 real-time kernels on the st20 /* 0 return address */ /* -1 entry point */ /* -2 undefined */ /* -3 undefined */ /* -4 undefined */ /* -5 undefined */ /* -6 task descriptor */ /* */ /***********************************************************/ }}} { {{{ locals extern const volatile void* _params; task* task; unsigned int* stack; int i; int* paramlist = (int*)((char*)¶mwords + size- of(int)); params* globalparams = (params*)_params; }}} {{{ check the task list if (taskcount >= max_tasks) return null; task = tasklist[taskcount]; }}} {{{ malloc task stack if (stacksize < default_stack_size) stacksize = default_stack_size; stack = (unsigned int*)malloc (stacksize); if (stack == null) return null; }}}
58/60 real-time kernels on the st20 {{{ initialise task structure task->t_id = taskcount++; task->t_state = t_created; task->t_stack_base = stack; task->t_stack_size = stacksize; task->t_wptr = (workspace)((byte*)stack + (stacksize - (bytes_per_word * (paramwords + 4)))); task->t_priority = priority; }}} {{{ initialise positive workspace with params and return ad- dress task->t_wptr[0] = (int)task_end; /* return address */ task->t_wptr[1] = (int)globalparams->gsb; /* global static base */ for (i = 0; i < paramwords; i++) task->t_wptr[i + 2] = paramlist[i]; }}} {{{ initialise negative workspace ready to start task->t_wptr[pw_iptr] = (int)function; task->t_wptr[pw_task] = (int)task; }}} {{{ register with inquest if necessary /* #ifdef inquest { int childiptr, parentwptr; __asm { ldlp 0; st parentwptr; ld (int)task->t_wptr; ldnl -1;
59/60 real-time kernels on the st20 st childiptr; } imsrtl_informthreadbirth ((void*)childiptr, (void*)parentwptr, (void*)task->t_stack_base, (void*)(task->t_stack_base + task- >t_stack_size)); } #endif */ }}} {{{ start the task task->t_state = t_active; activetasks++; __asm { ld (int)task->t_wptr; ldpri; or; runp; /* this will cause a trap and put the task on the correct queue */ } }}} return task; } }}} {{{ task* task_id (void) task* task_id (void) { return *currenttaskptr; } }}} {{{ int task_priority (int delta)
60/60 real-time kernels on the st20 int task_priority (int delta) { int oldpriority, newpriority; oldpriority = *currentpriorityptr; newpriority = oldpriority + delta; if (newpriority > max_user_priority) newpriority = max_user_priority; else if (newpriority < min_user_priority) newpriority = min_user_priority; if (newpriority != oldpriority) { (*currenttaskptr)->t_priority = newpriority; __asm {timeslice;} } return oldpriority; } }}} }}} information furnished is believed to be accurate and reliable. however, sgs-thomson microelectronics assumes no responsibility for the consequences of use of such information nor for any infringement of patents or other rights of third parties which may result from its use. no license is granted by implication or otherwise under any patent or patent rights of sgs- thomson microelectronics. specification mentioned in this publication are subject to change without notice. this publication supersedes and replaces all information previously supplied. sgs-thomson microelectronics products are not authorized for use as critical components in life support devices or systems without express written approval of sgs-thom son microelectronics. ? 19 96 sgs-tho mson microelectronics - printed in italy - all rights reserved. sgs-thomson microelectronics group of compani es australia - brazil - canada - china - france - germany - hong kong - italy - japan - korea - malaysia - malta - morocco - the netherlands - singapore - spain - sweden - switzerland - taiwan - thailand - united kingdom - u.s.a.

▲Up To Search▲

Price & Availability of AN860

	To Download AN860 Datasheet File
If you can't view the Datasheet, Please click here to try to view without PDF Reader .